1. Field of the Invention
This invention relates generally to multiprocessing digital computer systems and particularly to methods and systems for passing large messages between concurrently executing processes and for synchronizing concurrently executing processes.
2. Background Information
Processes are the most widely used unit of computation in computer programming and computer systems. Much of the work of an operating system of a computer is to provide an environment in which application programmers can define processes, execute them, and generally control their behavior. A process is a sequential unit of computation. The action of the unit of computation is described by a set of instructions executed sequentially on a Von Neumann computer, using a set of data associated with the process. The components of a process are the program to be executed, the data on which the program will execute, resources required by the program (for example, memory), and the status of the execution. For the process to execute, it must have a suitable environment including an engine for executing the program, memory for storing the program and data, and status information indicating the progress of the process. In contemporary computer systems, individual application programs may be implemented as a set of processes. These processes usually must be able to share information and/or synchronize their operation. There are a number of design strategies to allow multiple processes to communicate with one another. One possible strategy, called cooperative processing, is to allow the processes to have their own computer systems, requiring that the processes communicate with one another using a message-passing paradigm. For this approach to be effective, the communication mechanism must be very efficient If the processes need to communicate frequently, that is, they are fine-grained computations, then the network will likely be a bottleneck in the overall performance of the system. Another strategy is to allow the processes to share memory yet have their own Central Processing Unit (CPU) and control unit, thereby allowing interprocess communication (IPC) to take place in the common memory. This strategy is called multiprocessing. A third strategy, called multiprogramming, is to allow the processes to share memory and a single processor. In all of these strategies, supporting concurrent processes is difficult due to the need to share information among the processes. Efficiency in sharing information between processes and synchronizing processes is crucial.
Message-based interprocess communication (IPC) mechanisms have been employed in multiprogrammed uniprocessors and shared memory multiprocessors. In these mechanisms, messages are used to synchronize processes and to transmit information among a set of processes. A message contains a block of information formatted by a sending process in such a manner that it is meaningful to the receiving process. The message data may or may not be displayable on a computer display. It may consist of a portion of a file, an entire file, a collection of partial files, a collection of entire files, etc. In some existing systems, messages are kept in an area of memory that is shared by the processes. With this strategy, both the sending process and the receiving process always have access to a message. The shared memory scheme works without the need for copying the message, but the sending process is not prevented from (either accidentally or maliciously) modifying the data while the receiving process is processing the message. In addition, the receiving process can (accidentally or maliciously) modify the data while the sending process is preparing the message. This lack of security protection for the message is a significant limitation on such systems.
In other existing systems, messages are transmitted from one process to another by copying the body of the message from the memory of the sending process into the memory of the receiving process. If the receiving process is not ready to receive a message transmitted to it, some mechanism for temporarily storing the message is needed. In this situation, the operating system often will rely on the receiving process having a mailbox in which messages can be stored prior to the receiving process executing specific instructions to process the message. Thus, the typical path of information flow for passing a message from one process to another is as follows. The message is copied from the sending process's memory into the receiving process's mailbox, and then copied from the mailbox to the receiver's memory when the receiving process calls for the message. In general, two copy operations will need to be performed.
The receiving process's mailbox may be located in the operating system's memory or in the receiving process's memory. If it is located in the operating system memory, then mailboxes are a system resource that must be allocated to processes as required. If the mailbox is located in the receiving process's memory, then the operating system must rely on the receiving process to allocate the appropriate amount of memory, manage access to the mailbox, deallocate memory as required, etc.
An important limitation on message passing systems where the sending and receiving processes are prevented concurrent access to the message is the necessity of one or more iterations of copying the message data from one block of memory to another in order to pass the data between processes. The copying is necessary to ensure that the receiving process obtains an incorruptible message. These message passing systems use additional memory and limit overall system performance because of the time spent copying message data. The negative impact on performance of the message copy is insignificant for small messages. However, the cost of the message copy grows linearly with the size of the message. When the messages passed between processes become very large, such as is the case for large file transfers occurring in file transfer, graphics, and multimedia applications, system throughput suffers. The transfer of such messages, from 10,000 bytes for low resolution monochrome images to 10,000,000 bytes for high resolution E-size graphics, places a severe strain on the computer system's ability to provide output to an end-user in a timely fashion. A new mechanism that eliminates the copying of message data for communication between concurrently executing, cooperating processes yet provides adequate message data security is needed.